Міністерство освіти і науки України Львівський національний університет імені Івана Франка
Звіт про виконання лабораторної роботи №5:
«Особливості реалізації пошуку в ширину в графах»
Львів 2016
Завдання до роботи № 5.
Тема роботи: Особливості реалізації пошуку в ширину у графах.
Вихідні дані:
Задано:
– звичайний розгалужений граф (не менше 4-5и гілок) порядку 15-20 розміром 20-30;
– початкова і цільова вершини графа;
– напрям обходу.
Завдання:
– візуально представити заданий граф;
– знайти найкоротший шлях, використовуючи алгоритм пошуку в ши-рину;
– створити програму виконання пошуку на одній з мов об’єктно-орієнтованого програмування;
– відмітити переваги і недоліки цього виду пошуку.
Вимоги:
у програмі передбачити:
– можливість змінювати розмірність і порядок графа;
– можливість змінювати напрям обходу графа;
– зреалізувати візуалізацію процесу пошуку і його результатів.
Теоретичні відомості
Відповідно до використання евристичної інформації алгоритми діляться на два класи – сліпі та евристичні (спрямовані).
У сліпих алгоритмах пошуку місцезнаходження в просторі цільової вершини ніяк не впливає на порядок, в якому розкриваються (перебираються) вершини.
Сліпий метод має два види пошуку –пошук углиб і пошук вшир.
При пошуку вширину на фіксованому рівні досліджуються всі альтернативи і лише після цього здійснюється перехід на наступний рівень. Метод може виявитися гіршим за метод пошуку вглибину, якщо в графі всі шляхи, що ведуть до цільової вершини, розташовані приблизно на одній і тій же глибині.
При пошуку углибинукожна альтернатива досліджується до кінця, без урахування решти шляхів. Метод поганий для "високих" дерев, оскільки легко можна прослизнути мимо потрібної гілки і витратити багато зусиль на дослідження "порожніх" альтернатив.
Метод повного перебору в ширину.
Вершини в цьому методі пошуку розкриваються в тому порядку, в якому вони будуються(рис. 1).
Основний алгоритм полягає у виконанні наступних дій.
/
Рис. 1. Порядок обходу вершин графа при пошуку у ширину.
1. Початкова вершина (S1 на рис. 6) розкривається до тих пір, поки її можна розкрити, застосовуючи один і той же (або різні, дивлячись за умовою) оператор. При цьому утворюються вершини першого рівня (S2, S3, S4). Вони розкриваються в свою чергу і утворюються вершини дру-гого рівня (S5, S6, S7, S8) і т. д.
2. Розставляються вказівники, що ведуть від нових вершин до кореня.
3. Перевіряється, чи немає серед отриманих вершин цільової – якщо є, то формується рішення на основі відповідного оператора. Якщо цільових вершин немає, то розглядається перша породжена вершина і до неї застосовується той же алгоритм.
4. Після чого переходять до другої і т. д., поки серед одержуваних вершин не опиниться цільова.
Повний перебір в ширину гарантує знаходження цільової вершини як-раз тому, що перебір повний: –якщо цей шлях взагалі існує, при переборі вшир неодмінно буде знайденийнайкоротший шлях до цільової вершини, причому швидше, ніж інші шляхи. Шляхів досягнення мети, взагалі кажучи, може бути багато. У цьому випадку є можливість вибрати найліпший (найде-шевший/найлегший/швидкий і т. п. ) шлях. Але може бути випадок, коли граф пошуку виявиться нескінченним, і тоді цей алгоритм ніколи не скінчить роботу. Існує клас задач, для яких даний метод пошуку ефективний.
Для виконання роботи було написано програму в середовищі Visual Studio 2015 мовою C#.
Дана програмна реалізація алгоритму показує процес знаходження шляху в графі за допомогою алгоритму пошуку в ширину з порядком обходу: зліва направо та справа наліво. На рис. 1 бачимо загальний вигляд початкового вікна програми.
/
Рис. 1. Початкове вікно програми.
Для початку роботи необхідно вибрати граф, натиснувши відповідну кнопку, вибрати порядок обходу: «Від молодшого біта до старшого», або «Від старшого біта до молодшого», також ввести номер початкової та цільової вершин. Натиснути кнопку «Пошук» для запуску пошуку по графі. Зеленим позначено ребра біля не розкритих вершин графа. Фіолетовим ребра біл...
